package com.dyz.leetcode._20_dynamicProgramming;

public class _647_countSubstrings {
    public int countSubstrings(String s) {
        if(s==null || s.length()==0){return 0;}
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String subStr = s.substring(i , j+1);
                if(isPalindname(subStr)){
                    res++;
                }
            }
        }
        return res;
    }

    private boolean isPalindname(String s){
        int i=0;
        int j=s.length()-1;
        while (i<j){
            if(s.charAt(i)!=s.charAt(j)){return false;}
            i++;
            j--;
        }
        return true;
    }


    //使用动态规划
    public int countSubstrings1(String s) {
        if(s==null || s.length()==0){return 0;}
        boolean[][] dp = new boolean[s.length()][s.length()];
        //初始化
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
            res++;
        }
        //状态转移
        for (int j = 1; j < s.length(); j++) {//列
            for (int i = 0; i < j; i++) { //行
                boolean isCharE = s.charAt(i)==s.charAt(j);
                if(j-i==1){
                    dp[i][j] = isCharE;
                }else if(!isCharE){
                    dp[i][j] = isCharE;
                }else {
                    dp[i][j] = dp[i+1][j-1];
                }

                if(dp[i][j]){res++;}
            }
        }
        return res;
    }
}
